package newcoder.t1;

import jdk.nashorn.internal.ir.WhileNode;
import sun.dc.pr.PRError;

import java.util.ArrayList;
import java.util.HashSet;
import java.util.List;
import java.util.Set;

public class Solution {

    public static void main(String[] args) {
        ListNode a = new ListNode(1);
        ListNode b = new ListNode(2);
        a.next = b;
        ArrayList<Integer> integers = printListFromTailToHead(a);
        integers.forEach(i -> {
            System.out.println(i);
        });
    }

    public static ArrayList<Integer> printListFromTailToHead(ListNode listNode) {

        if (listNode == null) {
            return new ArrayList<>();
        }
        ListNode current = listNode.next;
        ListNode prev = listNode;
        ListNode next;

        while (current != null) {
            next = current.next;
            current.next = prev;
            prev = current;
            current = next;
        }
        listNode.next = null;
        ArrayList<Integer> list = new ArrayList<>();
        list.add(prev.val);
        while (prev.next != null) {
            list.add(prev.next.val);
            prev = prev.next;
        }

        return list;
    }

    public ListNode ReverseList(ListNode head) {
        if (head == null || head.next == null) {
            return head;
        }
        ListNode current = head.next;
        ListNode prev = head;
        ListNode next;
        while (current != null) {
            next = current.next;
            current.next = prev;
            prev = current;
            current = next;
        }
        head.next = null;
        return prev;
    }

    public ListNode Merge(ListNode list1, ListNode list2) {
        if (list1 == null) {
            return list2;
        }
        if (list2 == null) {
            return list1;
        }
        ListNode head;
        if (list1.val <= list2.val) {
            head = list1;
            list1 = list1.next;
        } else {
            head = list2;
            list2 = list2.next;
        }
        ListNode current = head;
        while (list1 != null && list2 != null) {
            if (list1.val <= list2.val) {
                current.next = list1;
                list1 = list1.next;
            } else {
                current.next = list2;
                list2 = list2.next;
            }
            current = current.next;
        }
        if (list1 != null) {
            current.next = list1;
        }
        if (list2 != null) {
            current.next = list2;
        }
        return head;
    }


    public ListNode FindFirstCommonNode(ListNode pHead1, ListNode pHead2) {
        if (pHead1 == null || pHead2 == null) {
            return null;
        }
        ListNode l1 = pHead1;
        ListNode l2 = pHead2;
        int length1 = 1;
        int length2 = 1;
        while (l1.next != null) {
            l1 = l1.next;
            length1++;
        }
        while (l2.next != null) {
            l2 = l2.next;
            length2++;
        }
        if (l1 != l2) {
            return null;
        }
        if (length1 < length2) {
            int d = length2 - length1;
            for (int i = 1; i <= d; i++) {
                pHead2 = pHead2.next;
            }
        } else if (length2 < length1) {
            int d = length1 - length2;
            for (int i = 1; i <= d; i++) {
                pHead1 = pHead1.next;
            }
        }
        while (pHead1 != pHead2) {
            pHead1 = pHead1.next;
            pHead2 = pHead2.next;
        }
        return pHead1;
    }

    public ListNode EntryNodeOfLoop(ListNode pHead) {
        ListNode slow = pHead;
        ListNode fast = pHead;
        while (true) {
            slow = slow.next;
            fast = fast.next;
            if (fast == null) {
                return null;
            }
            fast = fast.next;
            if (fast == null) {
                return null;
            }
            if (fast == slow) {
                break;
            }
        }
        while (pHead != fast) {
            pHead = pHead.next;
            fast = fast.next;
        }
        return pHead;
    }

    public ListNode FindKthToTail(ListNode pHead, int k) {
        if (pHead == null || k == 0) {
            return null;
        }
        List<ListNode> list = new ArrayList<>();
        while (pHead != null) {
            list.add(pHead);
            pHead = pHead.next;
        }
        int index = list.size() - k;
        if (index >= 0) {
            return list.get(index);
        } else {
            return null;
        }
    }

    public ListNode deleteNode(ListNode head, int val) {
        // write code here
        ListNode prev = null;
        ListNode current = head;
        ListNode next = current.next;
        while (current != null) {
            if (current.val == val) {
                if (prev == null) {
                    return next;
                } else {
                    prev.next = next;
                    return head;
                }
            } else {
                prev = current;
                current = next;
                next = current.next;
            }
        }
        return null;
    }
    //1,1,2,3,3,4,5,5


    public ListNode deleteDuplication(ListNode pHead) {

        ListNode virtual = new ListNode(0);
        virtual.next = pHead;
        ListNode prev = virtual;
        ListNode current = pHead;
        ListNode last = virtual;
        while (current != null) {
            ListNode next = current.next;
            if (next != null) {
                if (current.val != prev.val && current.val != next.val) {
                    last.next = current;
                    last = current;
                }
            }
            else{
                if (current.val != prev.val){
                    last.next = current;
                    last = current;
                }
                else{
                    last.next = null;
                }
            }
                prev = current;
                current = current.next;
        }
        if (last == virtual){
            return null;
        }
        else{
            return virtual.next;
        }
    }

}


class ListNode {
    int val;
    ListNode next = null;

    ListNode(int val) {
        this.val = val;
    }
}